package algorithmic_data_structure.二叉树递归套路;

import java.util.ArrayList;

public class Code02_MaxSubBSTHead {

	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(int data) {
			this.value = data;
		}
	}

	public static int getBSTSize(TreeNode head) {
		if (head == null) {
			return 0;
		}
		ArrayList<TreeNode> arr = new ArrayList<>();
		in(head, arr);
		for (int i = 1; i < arr.size(); i++) {
			if (arr.get(i).value <= arr.get(i - 1).value) {
				return 0;
			}
		}
		return arr.size();
	}

	public static void in(TreeNode head, ArrayList<TreeNode> arr) {
		if (head == null) {
			return;
		}
		in(head.left, arr);
		arr.add(head);
		in(head.right, arr);
	}

	public static TreeNode maxSubBSTHead1(TreeNode head) {
		if (head == null) {
			return null;
		}
		if (getBSTSize(head) != 0) {
			return head;
		}
		TreeNode leftAns = maxSubBSTHead1(head.left);
		TreeNode rightAns = maxSubBSTHead1(head.right);
		return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
	}

	public static TreeNode maxSubBSTHead2(TreeNode head) {
		if (head == null) {
			return null;
		}
		return process(head).maxSubBSTHead;
	}

	// 每一棵子树
	public static class Info {
		public TreeNode maxSubBSTHead;
		public int maxSubBSTSize;
		public int min;
		public int max;

		public Info(TreeNode h, int size, int mi, int ma) {
			maxSubBSTHead = h;
			maxSubBSTSize = size;
			min = mi;
			max = ma;
		}
	}

	public static Info process(TreeNode X) {
		if (X == null) {
			return null;
		}
		Info leftInfo = process(X.left);
		Info rightInfo = process(X.right);
		int min = X.value;
		int max = X.value;
		TreeNode maxSubBSTHead = null;
		int maxSubBSTSize = 0;
		if (leftInfo != null) {
			min = Math.min(min, leftInfo.min);
			max = Math.max(max, leftInfo.max);
			maxSubBSTHead = leftInfo.maxSubBSTHead;
			maxSubBSTSize = leftInfo.maxSubBSTSize;
		}
		if (rightInfo != null) {
			min = Math.min(min, rightInfo.min);
			max = Math.max(max, rightInfo.max);
			if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
				maxSubBSTHead = rightInfo.maxSubBSTHead;
				maxSubBSTSize = rightInfo.maxSubBSTSize;
			}
		}
		if ((leftInfo == null ? true : (leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.value))
				&& (rightInfo == null ? true : (rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.value))) {
			maxSubBSTHead = X;
			maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
					+ (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
		}
		return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
	}

	static class Ret{
		int min;
		int max;
		TreeNode maxBSTHead;
		int maxBSTSize;

		public Ret(int min, int max, TreeNode maxBSTHead, int maxBSTSize) {
			this.min = min;
			this.max = max;
			this.maxBSTHead = maxBSTHead;
			this.maxBSTSize = maxBSTSize;
		}
	}
	public static TreeNode maxBSTHead(TreeNode root){
		return process(root).maxSubBSTHead;
	}

	public static TreeNode maxBSTHead3(TreeNode root){
		return process7(root).maxBSTHead;
	}

	private static Ret process7(TreeNode root) {
		if (root == null){
			return null;
		}
		Ret leftRet = process7(root.left);
		Ret rightRet = process7(root.right);
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		TreeNode maxBSTHead = root;//默认是自己，如果左右都是空那就是自己了
		int maxBSTSize = 1;
		if (leftRet != null){
			max = leftRet.max;
			maxBSTHead = leftRet.maxBSTHead;
			maxBSTSize = leftRet.maxBSTSize;
		}
		if (rightRet != null){
			min = rightRet.min;
			if (rightRet.maxBSTSize > maxBSTSize){
				maxBSTHead = leftRet.maxBSTHead;
				maxBSTSize = leftRet.maxBSTSize;
			}
		}
		//判断左右 是否为 BST ，如果都是最大的头肯定是自己啊
		if (
				(leftRet == null ? true : (leftRet.maxBSTHead == root.left && leftRet.max <= root.value))
						&&
						(rightRet == null ? true : (rightRet.maxBSTHead == root.right && rightRet.min >= root.value))
				){
			maxBSTHead = root;
			maxBSTSize =
					(leftRet == null ? 0 : leftRet.maxBSTSize) + (rightRet == null ? 0 : rightRet.maxBSTSize) + 1;
		}
		return new Ret(min,max,maxBSTHead,maxBSTSize);
	}

	// for test
	public static TreeNode generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static TreeNode generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		TreeNode head = new TreeNode((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
		int maxLevel = 4;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			TreeNode head = generateRandomBST(maxLevel, maxValue);
			if (maxSubBSTHead1(head) != maxSubBSTHead2(head)) {
				if (maxSubBSTHead1(head) != maxBSTHead3(head)){
					System.out.println("Oops!");
				}
			}
		}
		System.out.println("finish!");
	}

}
